Home | | Latest | About | Random
# 20 Basis sets of a set, and dimension.
## Definitions.
Recall we have the ideas of a set of vectors being a **spanning set** for a collection of vectors, as well as a set of vectors being **linearly independent.** Let us briefly review:
- A set (or list) of vector $\{v_{1}.v_{2},\ldots,v_{n}\}$ is a **spanning set** for a collection of vectors $S$ if $$
\operatorname{span} \{v_{1},v_{2},\ldots,v_{n}\} = S.
$$This means, every vector in $S$ is a linear combination of vectors $v_{1},v_{2},\ldots,v_{n}$, **and** every linear combination of $v_{1},v_{2},\ldots,v_{n}$ is in $S$.
- A set (or list) of vector $\{v_{1},v_{2},\ldots,v_{n}\}$ is **linearly independent** if the equation $$
c_{1}v_{1}+c_{2}v_{2}+ \cdots + c_{n}v_{n}=\mathbf{0}
$$has **only** the trivial solution (no nontrivial linear combination for $\mathbf{0}$). Equivalently this means no one vector is a linear combination of the other vectors. And morally this means "there is no redundancy among them".
Now if we have such a list of vector $\{v_{1},v_{2},\ldots,v_{n}\}$ that is **both** (1) a spanning set for $S$, and (2) linearly independent, then we say this list of vector $\{v_{1}.v_{2},\ldots,v_{n}\}$ forms a **basis set** for $S$.
**Remark.** It is possible for a set $S$ to have **no** basis set whatsoever. As it turns out only "special kinds of sets of vectors" have basis sets, these are called **linear spaces**, which we will devote our attention later.
**Remark.** It is also possible for a set $S$ to have **many different** basis sets (bases). What is remarkable, however, is that despite there are many different basis sets for a set $S$, the **number of element in each of these basis sets for $S$ is invariant, namely it is always the same!** This common number is called the **dimension** of $S$, denote as $\dim(S)$.
## Examples and concrete computation.
Let us see some concrete explicit examples of basis sets for sets, and how to show they are indeed bases.
**Example.**
Let us consider the set of all vectors in $\mathbb{R^{2}}=\{\begin{pmatrix}x\\y\end{pmatrix}:x,y\in \mathbb{R}\}$. As it turns out, the vectors $e_{1}=\begin{pmatrix}1\\0\end{pmatrix}$ and $e_{2}=\begin{pmatrix}0\\1\end{pmatrix}$ together forms a basis for $\mathbb{R}^{2}$. That is, $$
\{e_{1},e_{2}\} \text{ forms a basis set for \(\mathbb R^2,\)}
$$in particular, we can check and show that:
- $\operatorname{span}\{e_{1},e_{2}\} = \mathbb{R}^{2}$, so $\{e_{1},e_{2}\}$ is a spanning set for $\mathbb{R}^{2}$, and
- $\{e_{1},e_{2}\}$ is linearly independent.
- Therefore $\{e_{1},e_{2}\}$ is a basis for $\mathbb{R}^{2}$, and $\mathbb{R}^{2}$ has dimension 2, and we write $\dim(\mathbb{R}^{2})=2$.
Let us actually show this!
(1) $\{e_{1},e_{2}\}$ is a **spanning set of $\mathbb{R}^{2}$**:
To show this, we need to show $\operatorname{span}(e_{1},e_{2})=\mathbb{R}^{2}$. This means we need to show two sets are the same. Let us do mutual set containment.
Take an element $v\in \operatorname{span}(e_{1},e_{2})$. Then $v=c_{1}e_{1}+c_{2}e_{2}=\begin{pmatrix}c_{1}\\c_{2}\end{pmatrix}$. Note $v$ is in $\mathbb{R^{2}}$. Hence we have $\operatorname{span}(e_{1},e_{2})\subset \mathbb{R}^{2}$.
Take an element $v\in \mathbb{R^{2}}.$ Then $v=\begin{pmatrix}x\\y\end{pmatrix}$ for some $x,y\in \mathbb{R}$. Note that $v = x e_{1}+ye_{2}$, hence $v=\operatorname{span}(e_{1},e_{2})$. Thus $\mathbb{R^{2}} \subset \operatorname{span}(e_{1},e_{2})$.
So this shows $\operatorname{span}(e_{1},e_{2}) = \mathbb{R^{2}}$, in other words, $\{e_{1},e_{2}\}$ is a spanning set for $\mathbb{R}^{2}$.
(2) $\{e_{1},e_{2}\}$ is **linearly independent**:
To show this, we need to consider the linear equation $$
c_{1}e_{1}+c_{2}e_{2}=\mathbf{0}.
$$But if we expand the left hand side we get $$
\begin{pmatrix}c_{1}\\c_{2}\end{pmatrix} = \mathbf{0} = \begin{pmatrix}0\\0\end{pmatrix},
$$which shows we only have $c_{1}=c_{2}=0$ as solution. Hence $\{e_{1},e_{2}\}$ is linearly independent!
(3) Hence $\{e_{1},e_{2}\}$ is a **basis** for $\mathbb{R}^{2}$, and since there are 2 elements in this basis set, we deduce $\dim(\mathbb{R}^{2})=2$. $\blacklozenge$
**Example.**
We remark there can be **many different basis sets** for the same set! Here we will illustrate that $$
\beta =\{\begin{pmatrix}1\\2\end{pmatrix},\begin{pmatrix}2\\1\end{pmatrix}\}
$$is a basis set for $\mathbb{R}^{2}$.
Again we need to show:
- $\beta$ is a spanning set for $\mathbb{R}^{2}$, and
- $\beta$ is linearly independent.
Let us do it.
(1) $\beta$ is a spanning set for $\mathbb{R}^{2}$. To show this, we need to show $\operatorname{span}(\beta)= \mathbb{R}^{2}$. Ok, this is a mutual set containment.
Take an element $v\in \operatorname{span}(\beta)=\operatorname{span}\{\begin{pmatrix}1\\2\end{pmatrix},\begin{pmatrix}2\\1\end{pmatrix}\}$. Then $v=c_{1}\begin{pmatrix}1\\2\end{pmatrix}+c_{2}\begin{pmatrix}2\\1\end{pmatrix} = \begin{pmatrix}c_{1}+2c_{2}\\2c_{1}+c_{2}\end{pmatrix}$, which is an element of $\mathbb{R}^{2}$. Hence $v \in \mathbb{R}^{2}$. This shows $\operatorname{span}(\beta) \subset \mathbb{R}^{2}$.
Now take an element $v \in \mathbb{R}^2$, then $v=\begin{pmatrix}x \\ y\end{pmatrix}$ for some fixed $x,y \in \mathbb{R}$. We need to show $v\in \operatorname{span}(\beta)$, that is, we need to show $v$ is some linear combination of $\begin{pmatrix}1\\2\end{pmatrix}$ and $\begin{pmatrix}2\\1\end{pmatrix}$. To see this, we consider the linear system $$
c_{1}\begin{pmatrix}1\\2\end{pmatrix} +c_{2}\begin{pmatrix}2\\1\end{pmatrix} = \begin{pmatrix}x\\y\end{pmatrix}
$$and we need to show it is **consistent**. (Note here $x,y$ are **fixed** and we are solving for $c_{1}$ and $c_{2}$.) Indeed, if we set up the augmented matrix, we see that $$
\begin{bmatrix}1 & 2 & \vdots & x \\
2 & 1 & \vdots & y\end{bmatrix} \stackrel{\text{row}}\sim \begin{bmatrix}1 & 2 & \vdots & x \\
0 & -3 & \vdots & y-2x\end{bmatrix},
$$which we see is consistent. Hence $\begin{pmatrix}x\\y\end{pmatrix}\in \operatorname{span}\{\begin{pmatrix}1\\2\end{pmatrix},\begin{pmatrix}2\\1\end{pmatrix}\}$.
So we conclude that $\operatorname{span}(\beta)=\mathbb{R}^{2}$, and that $\beta$ is indeed a spanning set for $\mathbb{R}^2$.
(2) $\beta$ is linearly independent. To show this, we need to show the equation $$
c_{1}\begin{pmatrix}1\\2\end{pmatrix}+c_{2}\begin{pmatrix}2\\1\end{pmatrix} = \mathbf{0}
$$has only the trivial solution. Let us set up the augmented matrix $$
\begin{bmatrix}1 & 2 & \vdots & 0 \\
2 & 1 & \vdots & 0\end{bmatrix}\stackrel{\text{row}}\sim \begin{bmatrix}1 & 2 & \vdots & 0 \\
0 & -3 & \vdots & 0\end{bmatrix},
$$which we see have **only unique solution**, whence this homogeneous equation must only have the trivial solution. Hence $\beta$
is linearly independent!
Whence we have shown $\beta = \{\begin{pmatrix}1\\2\end{pmatrix},\begin{pmatrix}2\\1\end{pmatrix}\}$ is a basis for $\mathbb{R}^{2}$.
And, perhaps not too surprising, this agrees with $\dim(\mathbb{R}^{2}) = 2$. $\blacklozenge$
**Example.**
Not every set has a basis set! Only special kinds of sets called **"linear spaces"** do. In particular, in order to have a basis set, it must have a spanning set. **So only sets that is the span of some set have basis sets!** (In fact this is a characterization of linear spaces -- a set expressible as a span of some set of vectors!) Furthermore, since the zero vector $\mathbf{0}$ is always in the span of some set, if a set does not contain the appropriate zero vector, then it is not a linear space and cannot have a basis set.
Let us look at $L = \{\begin{pmatrix}t\\t+1\end{pmatrix}:t\in \mathbb{R}\}$. This is a collection of vectors that lie on the line $y=x+1$. Note we can write $L=\operatorname{span}\{\begin{pmatrix}1\\1\end{pmatrix}\} + \begin{pmatrix}0\\1\end{pmatrix}$, but we can never write $L$ as the span of some set of vectors only. Since if $L$ is the span of some set, it would contain the zero vector $\mathbf{0}=\begin{pmatrix}0\\0\end{pmatrix}$, but $L$ does not contain $\begin{pmatrix}0\\0\end{pmatrix}$! Hence $L$ does not have a basis set (and in fact $L$ is not a linear space)
**Remark.** This set $L=\operatorname{span}\{\begin{pmatrix}1\\1\end{pmatrix}\} + \begin{pmatrix}0\\1\end{pmatrix}$ is not a linear space, but it is a translation of a linear space. Translations of linear spaces are called **affine spaces**. If one recall, solutions to nonhomogeneous linear equations are these kinds, they are in fact all affine spaces, whilst solution to homogeneous linear equations are linear spaces.
**Example.** Some edge case scenarios. What about a singleton set containing just a zerovector of some kind? Say $S = \{\begin{pmatrix}0\\0\end{pmatrix}\}$. Well, since $S$ is the span of $\{\begin{pmatrix}0\\0\end{pmatrix}\}$, so it would have a basis. But what is a basis for $S$? It cannot be $\{\begin{pmatrix}0\\0\end{pmatrix}\}$ as this is linearly **dependent**. It is in fact the **empty set** $\{\}$ ! Indeed, recall we define that $\operatorname{span}\{\}$ to be $\{\mathbf{0}\}$, and that we also defined $\{ \}$ to be linearly independent. So we declare a basis set for $S = \{\begin{pmatrix}0\\0\end{pmatrix}\}$ is the empty set $\{ \}$, and since there is nothing in the empty set, we have $\dim(S)= 0$.
Let us see some more examples of basis sets but just "column vectors".
**Example.**
Show that $\beta = \{ \begin{pmatrix}1 & 1\\1 & 0\end{pmatrix} , \begin{pmatrix}0 & 1\\1 & 1\end{pmatrix}, \begin{pmatrix}1 & 0\\0 & 0\end{pmatrix} \}$ is a basis set for the set of matrices $G = \{\begin{pmatrix}a & b \\b & c\end{pmatrix}:a,b,c \in\mathbb{R}\}$. Note the kinds of matrices that are in $G$ follows a specific format.
Ok to show this, we need to show that
- $\beta$ is a spanning set for $G$, that is, $\operatorname{span}(\beta) = G$, and
- $\beta$ is linearly independent.
(1) To show $\operatorname{span}(\beta)=G$, we show mutual containment.
Take $A \in \operatorname{span}(\beta)$. Then $A =c_{1}\begin{pmatrix}1 & 1\\1 & 0\end{pmatrix} +c_{2}\begin{pmatrix}0 & 1\\1 & 1\end{pmatrix} + c_{3}\begin{pmatrix}1 & 0\\0 & 0\end{pmatrix}$. We need to show $A\in G$. Note $$
A = \begin{pmatrix}c_{1} + c_{3} & c_{1}+c_{2} \\ c_{1}+c_{2} & c_{2}\end{pmatrix}
$$and by looking at this form, we see that $A\in G$. So we have $\operatorname{span}(\beta)\subset G$.
Next, take $A\in G$, then $A=\begin{pmatrix}a & b\\b & c\end{pmatrix}$. We need to show $A \in \operatorname{span}(\beta)$, that $A$ is a linear combination of those three matrices. We set up the linear equation to check for consistency: $$
c_{1}\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix} +c_{2} \begin{pmatrix}0 & 1\\1 & 1\end{pmatrix} +c_{3}\begin{pmatrix}1 & 0\\0 & 0\end{pmatrix} = A=\begin{pmatrix}a & b\\b & c\end{pmatrix},
$$which gives the linear system $$
\begin{align*}
c_{1}+c_{3}=a \\
c_{1}+c_{2}=b \\
c_{1}+c_{2}=b \\
c_{3}=c
\end{align*}
$$This has augmented matrix $$
\begin{bmatrix}1 & 0 & 1 & \vdots & a \\
1 & 1 & 0 & \vdots & b \\
1 & 1 &0 & \vdots & b \\
0 & 0 & 1 & \vdots & c \end{bmatrix} \stackrel{\text{row}}\sim
\begin{bmatrix}1 & 0 & 1 & \vdots & a \\
0 & 1 & -1 & \vdots & b-a \\
0 & 0 & 1 & \vdots & c \\
0 & 0 & 0 & \vdots & 0\end{bmatrix}
$$which we see is **consistent**, hence $A$ is a linear combination of those three matrices, and hence $\operatorname{span}(\beta) \subset G$.
This shows $\operatorname{span}(\beta)=G$, and that $\beta$ is a spanning set for $G$.
(2) Next, we show $\beta$ is linearly independent. We set up the linear equation $$
c_{1}\begin{pmatrix}1 & 1\\1 & 0\end{pmatrix}+c_{2}\begin{pmatrix}0 & 1\\1 & 1\end{pmatrix}+c_{3}\begin{pmatrix}1 & 0\\0 & 0\end{pmatrix} = \mathbf{0}=\begin{pmatrix}0 & 0 \\0 & 0\end{pmatrix},
$$ which gives the linear system $$
\begin{align*}
c_{1}+c_{3}=0 \\
c_{1}+c_{2}=0 \\
c_{1}+c_{2}=0 \\
c_{3}=0
\end{align*}
$$And this gives the augmented matrix $$
\begin{bmatrix}1 & 0 & 1 & \vdots & 0 \\
1 & 1 & 0 & \vdots & 0 \\
1 & 1 &0 & \vdots & 0 \\
0 & 0 & 1 & \vdots & 0 \end{bmatrix} \stackrel{\text{row}}\sim
\begin{bmatrix}1 & 0 & 1 & \vdots & 0 \\
0 & 1 & -1 & \vdots & 0 \\
0 & 0 & 1 & \vdots & 0 \\
0 & 0 & 0 & \vdots & 0\end{bmatrix}
$$Since we see that this homogeneous linear system have **unique** solution, we only have the trivial solution $c_{1}=c_{2}=c_{3}=0$. Hence $\beta = \{ \begin{pmatrix}1 & 1\\1 & 0\end{pmatrix} , \begin{pmatrix}0 & 1\\1 & 1\end{pmatrix}, \begin{pmatrix}1 & 0\\0 & 0\end{pmatrix} \}$ is linearly independent.
Together this shows $\beta$ is a basis set for $G$. And we have $\dim(G)=3$. $\blacklozenge$
Now, it might not be super clear why we would adopt a particular basis set over the others, especially we have possibly multiple bases for the same set. In the next set of notes, we will illustrate a very specific choice of basis set $\beta$ for all $8 \times 8$ matrices, denoted $M_{8\times8}(\mathbb{R})$ in the context of **image compression**, which is the foundation of how jpeg images work!